package class09_01_trieTree;
/*
* https://leetcode.cn/problems/implement-trie-prefix-tree/
* */

class Trie {
    Node root;
    class Node {
        int pass;//通过数
        int end;//结束个数
        Node[] childs;

        public Node(){
            pass=0;
            end=0;
            childs = new Node[26];//可能的26个字母，可能的26棵子树
        }
    }
    public Trie() {
        this.root = new Node();
    }

    public void insert(String word) {
        if(word==null) return;
        Node pointer = this.root;
        pointer.pass++;
        char[] chars = word.toCharArray();
        for(int i = 0;i<chars.length;i++){
            if(pointer.childs[chars[i]-'a']==null){//为空就新建子节点
                pointer.childs[chars[i]-'a']=new Node();
            }
            pointer=pointer.childs[chars[i]-'a'];
            pointer.pass++;
            if(i==chars.length-1)pointer.end++;
        }
    }

    public boolean search(String word) {
        if(word==null) return true;
        char[] chars = word.toCharArray();
        Node pointer = this.root;
        for(int i = 0;i<chars.length;i++){
            pointer=pointer.childs[chars[i]-'a'];
            if(pointer==null) return false;//中途有null代表没有
            if(i==chars.length-1){
                return pointer.end>0;//最后一个字母对应的结点end为0代表没有以这个结束的
            }
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        if(prefix==null) return true;
        char[] chars = prefix.toCharArray();
        Node pointer = this.root;
        for(int i = 0;i<chars.length;i++){
            pointer=pointer.childs[chars[i]-'a'];
            if(pointer==null) return false;
        }
        return true;
    }

    public void remove(String word){
        if(word==null || (!search(word))) return;
        char[] chars = word.toCharArray();
        Node pointer = this.root;
        for(int i = 0;i<chars.length;i++){
            pointer.childs[chars[i]-'a'].pass--;
            if(pointer.childs[chars[i]-'a'].pass==0){
                pointer.childs[chars[i]-'a']=null;//直接设空，JVM会把获取不到的引用置空
                return;
            }
            if(i==chars.length-1){pointer.childs[chars[i]-'a'].end--;}
            pointer=pointer.childs[chars[i]-'a'];
        }
    }
}
